package cn.cxq.learning.array;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;

/**
 * 链接：https://www.nowcoder.com/questionTerminal/9b4c81a02cd34f76be2659fa0d54342a
 * 来源：牛客网
 * <p>
 * [编程题]顺时针打印矩阵
 * 热度指数：906614时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
 * 算法知识视频讲解
 * 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
 * 示例1
 * 输入
 * [[1,2],[3,4]]
 * 输出
 * [1,2,4,3]
 */
public class PrintMatrixClockwise {

    @Test
    public void testPrintMatrix() {
        System.out.println(printMatrix(new int[][]{{1, 2}, {3, 4}}));
    }

    //递归法轻松解决
    public ArrayList<Integer> printMatrix(int[][] matrix) {

        ArrayList<Integer> result = new ArrayList<>();

        if (matrix.length == 0 || matrix[0].length == 0) {
            return result;
        }

        int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];

        result.add(matrix[0][0]);
        visited[0][0] = true;

        goMatrix(result, visited, matrix, 0, 0, directions, 0, 0);

        return result;
    }

    private void goMatrix(ArrayList<Integer> result, boolean[][] visited, int[][] matrix, int x, int y, int[][] directions, int group, int unMove) {

        if (unMove == 4) { //四个方向都没有走通就让结束递归
            return;
        }

        boolean move = false; //动了的话置为true

        int[] direction = directions[group];

        while (x + direction[0] >= 0 && x + direction[0] < matrix.length
                && y + direction[1] >= 0 && y + direction[1] < matrix[0].length
                && !visited[x + direction[0]][y + direction[1]]) {
            x += direction[0];
            y += direction[1];
            result.add(matrix[x][y]);
            visited[x][y] = true;
            move = true;
        }

        if (!move) {
            unMove++; //每次没有移动让他加一；
        } else {
            unMove = 0; //动了的话又将其清零
        }

        goMatrix(result, visited, matrix, x, y, directions, (group + 1) % 4, unMove);
    }
}
